package com.lwl.Algorithmic_data_structure.class24滑动窗口;

import java.util.LinkedList;

/**
 * @author lwl
 * @Description 给你一个数组，以及一个num，请你求出数组中有几个子数组满足：最大值-最小值 <= Num
 * @date 2023/6/24 21:59
 */
public class Code02AllLessNumSubArray {

    public static void main(String[] args) {
        System.out.println(getAllLessNumSubArray(new int[]{1, 2, 3}, 0));
        System.out.println(getAllLessNumSubArray(new int[]{1, 2, 3}, 1));
        System.out.println(getAllLessNumSubArray(new int[]{1, 2, 3}, 2));
    }

    public static int getAllLessNumSubArray(int[] array, int num) {
        if (array == null || array.length == 0 || num < 0) {
            return 0;
        }
        int res = 0;
        // 当前窗口内最大值为队列头（下标）
        LinkedList<Integer> minDoubleQueue = new LinkedList<>();
        // 当前窗口内最小值为队列头（下标）
        LinkedList<Integer> maxDoubleQueue = new LinkedList<>();
        int R = 0;
        for (int L = 0; L < array.length; L++) {
            // R右移到第一个不满足条件的位置，当前满足的子数组个数为 (R-1) - L + 1 => R - L
            while (R < array.length) {
                while (!minDoubleQueue.isEmpty() && array[R] <= array[minDoubleQueue.peekLast()]) {
                    minDoubleQueue.pollLast();
                }
                minDoubleQueue.addLast(R);
                while (!maxDoubleQueue.isEmpty() && array[R] >= array[maxDoubleQueue.peekLast()]) {
                    maxDoubleQueue.pollLast();
                }
                maxDoubleQueue.addLast(R);
                if (array[maxDoubleQueue.peekFirst()] - array[minDoubleQueue.peekFirst()] > num) {
                    break;
                } else {
                    R++;
                }
            }
            res += R - L;
            // 下一个大循环L会++，所以要将L下标过滤掉
            if (minDoubleQueue.peekFirst() == L) {
                minDoubleQueue.pollFirst();
            }
            if (maxDoubleQueue.peekFirst() == L) {
                maxDoubleQueue.pollFirst();
            }
        }
        return res;
    }

}
